The present invention relates generally to computer-aided methods of designing an electronic device and more particularly to a computer-aided method of designing a carry-lookahead adder.
An adder is a device that adds two binary numbers and an input-carry bit to produce a binary sum and an output-carry bit. Typically, there are two types of adders, a ripple adder and a carry-lookahead adder. A ripple adder propagates or ripples the carry bit of the adder from the least significant bit to the most significant bit, one bit at a time, to generate both the sum bit and the output-carry bit. A carry-lookahead adder produces the output-carry bit by simultaneously operating on the input-carry bit and some or all of the bits of the binary numbers.
FIG. 1 shows a part Y of a one-bit adder. It produces an output-carry bit C.sub.1 from input data bits a.sub.1 and b.sub.1 and an input-carry bit C.sub.2. The logic that produces the output sum bit of the adder is not shown in the figure. The logic product (AND) of the input data bits is called the generate bit G, and the logic sum (OR) of the input data bits is called the propagate bit P.
FIG. 2 shows a schematic diagram of a part of a four-bit ripple adder. Each rectangular box Y with a dashed outline can be substituted by the dashed box Y in FIG. 1. The output sum bits are again not shown in the Figure. The most significant bit is represented by the smallest subscript, whereas the least significant bit is represented by the largest subscript. To produce the output-carry bit C.sub.0, the input-carry bit C.sub.4 has to ripple through each one-bit adder; this rippling process delays the response time of the circuit.
A carry-lookahead adder takes less time to produce the sum and output-carry bits because it operates on some or all of the bits of the binary numbers in parallel. FIG. 3 shows part of a two-bit carry-lookahead adder (logic that produces the sum bits has been omitted). Each box marked X can be substituted by the box X in FIG. 1.
As the number of bits in each binary number increases, the complexity of the carry-lookahead adder increases. The box marked W in FIG. 3 has only a single level of AND gates, but as the number of bits increases, fan-in and fan-out limitations result in an increasing number of levels of gates. Even so, a carry-lookahead adder takes significantly less time to produce the output carry and sum bits than a ripple adder.
Increasing the number of bits of a ripple adder is easily accomplished by simply stringing additional one-bit adders together in series, following the pattern of FIG. 2. If the circuit is being designed by means of a computer-aided tool, all that is necessary is for a designer to inform the computer of the number of bits desired.
on the other hand, the design of a carry-lookahead adder changes as the number of bits changes, as shown by comparing FIGS. 3 to 4, a two-bit adder to a three-bits adder. In addition, fan-in and fan-out rules, which in general are different for different gate technologies, must be taken into account. For these reasons, changing or tuning a carry-lookahead adder during a typical design process can be quite tedious.
It would be beneficial if there were a method of designing a carry-lookahead adder automatically by means of a computer-aided system.